Reed-Solomon codes provide an easy way to generate t symbol correction codes requiring the addition of only 2*t parity symbols. However, the correction computation increases dramatically as the number of correctable symbols (t) is increased.
Much work has been done in the area of Reed-Solomon decoders when t is greater than one and many patents have been filed covering methods to handle this difficult operation. Schemes such as the Berlekamp-Massey and Euclidean algorithms have been developed to process syndrome bytes into Error-Locator and Error-Evaluator polynomials. The Chien Search and the Forney algorithm are typically used to extract the roots of these polynomials that are the error location and correction pattern information needed to correct each error.
The ability to correct multiple errors is an important capability in the communications field where burst errors in a communications channel are common due to various impulse noise sources. A method has been developed to handle large burst errors while avoiding the difficult decoding problems caused by increasing the size of t to handle larger and larger burst errors. An operation called interleaving is used to rearrange symbols prior to transmission so that succeeding symbols are covered by a different set of parity symbols. Using an interleave factor of five with a single error correcting code results in the ability to correct a burst of up to five consecutive symbol errors. When received and de-interleaved the burst of five symbol errors is transformed into five single symbol errors in five consecutive blocks.
Interleaving provides an easy way to extended the error correction capability of single error correcting codes while avoiding the hardware complexity and the added processing time of more powerful multi error correcting Reed-Solomon codes. In the following example each letter represents a single symbol in a data stream. The notation ‘vv’ represents the two parity symbols at the end of a block and each block covered by these two parity symbols consists of seven symbols. The example illustrates five separate blocks of data each covered by a single symbol correction code vv,ww,xx,yy,zz:    AAAAAAAvvBBBBBBBwwCCCCCCCxxDDDDDDDyyEEEEEEEzz
Interleaved symbols transmitted over a noisy communications channel may be illustrated as:    ABCDEABCDEABCDEABCDEABCDEABCDEABCDEvwxyzvwxvz
A burst error of five error symbols ‘#’ injected in the interleaved data stream as follows:    ABCDEABCDEABCDEABC#####DEABCDEABCDEvwxyzvwxyz
However, at the receiver end the blocks are De-Interleaved with each block having only a single correctable symbol error as follows:    AAAA#AAvvBBBB#BBwwCCCC#CCxxDDD#DDDyyEEE #EEEzz
The encoding process appends a set of 2t parity symbols to the end of each data block such that, in the absence of any errors, the receiver generated 2t syndromes are all zeroes.
Generation of the Reed-Solomon parity symbols is defined by a generator polynomial of the form g(x)=(x+αj) (x+αj+1) (x+αj+2) (x+α+3) . . . (x+αj +2t−2)(x+αj+2t−1). Where t defines the number of correctable errors, j is the starting exponent of α, and α is a prime element of GF(256). To be prime means that the log2(α) must have no common factors with the number 255 (i.e. 3, 5, or 17). The typical value used for α is 2.
For the class of single error Reed-Solomon codes where t=1 and α=2 the generator polynomial is of the form g(x)=(x+2j) (x+2j+1)=x2+(2j+2j+1)x+22j+1. Carrying out the indicated multiplication reveals the two coefficients (C1=2j+2j+1 and C0=22j+1) used to generate the two parity symbols for any selected value of j. Two commonly selected values for j are 0 and 1. The coefficients define the multipliers used to generate the parity symbols as shown in FIG. 1.
As shown in FIG. 1, generation of the n parity symbols is accomplished by XORing the received data with parity symbol Pn at XOR 2. The output of XOR 2 is then provided to multipliers 3 which operate on the data and provide the data to parity registers 4. The output of each successive parity register P0, P1 . . . Pn−1 is XORed with the output of each successive multiplier C1, C2 . . . Cn by XOR 5 and stored in the successive parity registers P1, P2 . . . Pn.
The use of single error correcting interleaved Reed-Solomon codes is specified in the downstream control path for several applications, including for example, Set-Top-Boxes, as defined by standards compliance documents DVS-167 and DVS-178. Set-Top-Boxes (STB) are used to connect a consumer's Television Set to the cable entering their home. The TV screen and STB remote control provide a means for the consumer to interact with the cable company through the STB in order to select and purchase TV programming.
The manufacturing cost of the STB is of critical importance in this application since STBs are typically provided to the cable customer at little or no charge. Cost of the final STB can be kept as low as possible by implementing each element that makes up a STB as efficiently as possible.
Speed of operation is also an important consideration for a correction scheme when applied to high-speed communication systems in order to minimize the time between receipt of data to generation of corrected data.